package leetcode_周赛._2023._08;

import general_class.ListNode;

import java.util.List;
import java.util.TreeSet;

/**
 * 第 358 场周赛
 * <p>AC_3</p>
 *
 * @author yezh
 * @date 2023/8/14 8:56
 */
public class _13 {

    /**
     * 2816.翻倍以链表形式表示的数字
     * <p>算法: 链表</p>
     */
    public ListNode doubleIt(ListNode head) {
        ListNode ans = new ListNode(0, head), cur = ans;
        while (cur != null) {
            cur.val = 2 * cur.val % 10;
            if (cur.next != null && cur.next.val >= 5) cur.val += 1;
            cur = cur.next;
        }
        return ans.val == 0 ? ans.next : ans;
    }

    /**
     * 2817.限制条件下元素之间的最小绝对值差
     * <p>算法: 滑动窗口</p>
     */
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        int n = nums.size(), ans = Integer.MAX_VALUE;
        TreeSet<Integer> treeSet = new TreeSet<>();
        // 不用判断获取的结果为空
        treeSet.add(Integer.MAX_VALUE);
        treeSet.add(Integer.MIN_VALUE / 2);
        for (int i = x; i < n; i++) {
            treeSet.add(nums.get(i - x));
            int num = nums.get(i);
            ans = Math.min(ans, Math.min(treeSet.ceiling(num) - num, num - treeSet.floor(num)));
        }
        return ans;
    }

}
